For “big data” applications, such as within a data center or cloud computing environment, large amounts of data need to be stored reliably and in a cost-effective manner. Compression processes are generally employed to reduce the size of data without sacrificing the information contained within the data. Data consumers are required to decompress the compressed files before using the data. Conventional compression formats for big data stores typically produce relatively poor compression ratios, for example, because they are fairly simplistic in an attempt to provide efficient software implementations, while also allowing for some degree of random access. Compression schemes such as Deflate offer better compression ratios, but current implementations do not allow for random access to compressed data. For example, column-oriented databases are often used in big data environments to provide the desired output. However, compressed column-oriented data requires decompression of a column of data from a start point to a point of interest to access the point of interest. Thus, random accesses on compressed big data stores using conventional techniques are generally cost and resource prohibitive.